1. Field of the Invention
This invention relates generally to computer networks, and more particularly to routers, switches and the like for computer network systems.
2. Description of the Related Art
Computers are increasingly being coupled together into computer networks. In larger networks, devices known as "routers" or "switches" direct the flow of data packets between source and destination computers. Since the "bandwidth" of routers is limited, various "queuing" techniques have been developed to prioritize the forwarding of packets by computer network routers.
Fair queuing techniques in packet scheduling applications and devices have been extensively researched and are described in a number of publications. Generally, network switches are configured to receive a number of packets at their input ports (i.e., ports of entry), where each packet is usually one among a sequence of many packets that constitute a flow. The switch directs a flow to an output port (i.e., port of exit). Often, a flow has some requirements on network bandwidth; for example, if the flow constitutes video information (e.g., a movie) and the source of the information (e.g., a VCR) generates 1.5 Mb/s of data, the flow would require that the network guarantee 1.5 Mb/s of bandwidth. This means that any switches that the flow passes through on its way from the source to the destination will have to guarantee 1.5 Mb/s of bandwidth to the flow. Similarly, a flow carrying high quality audio information (e.g., a concert) may require 128 Kb/s of bandwidth from the network.
However, each output port typically has a fixed amount of bandwidth (e.g., 100 Mb/s) available, and each output port in a switch has a number of output queues. In operation, the switch will sort the flows bound for a particular output port into different output queues at the output port, such that each output queue services a flow with a particular bandwidth requirement. The switch must then ensure that each output queue is provided with sufficient access too the output port so that the requirements of the associated flows are met.
The result of not meeting the bandwidth requirements of a flow is increased delay, often beyond the tolerance of the flow. In such a situation, the source of the flow will be generating information faster than the network can transfer it to the destination. This means that over the course of time, some packets will be delayed excessively, and will have to be dropped (i.e., discarded), either because packets that have been delayed too much are rendered useless in real-time audio and video applications, or because the network has run out of resources to buffer packets. In either case, the result is reduced quality of reception; the reduction in quality may vary from a minor inconvenience to total incapacitation.
The technique employed by a switch to ensure that the requirements of a flow are met is called "fair queuing." A problem with existing queuing techniques is that the algorithms involve a very high number of arithmetical computations, and any simplifications made to the algorithms for ease of implementation in hardware and software tend to introduce significant inaccuracies, some of which are difficult to quantify. Good examples of prior art fair queuing techniques can be found in the Ph.D. thesis of A. K. Parekh entitled "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks," Massachusetts Institute of Technology, LIDS-TH-2089, February 1992, which is incorporated herein by reference in its entirety. The Parekh thesis describes a theoretical generalized processor sharing (GPS) machine and the algorithms it uses to achieve fair queuing. The thesis also describes a more realistic scheme (PGPS) to implement the theoretical machine. In general, the PGPS computations are performed on a packet-by-packet basis to facilitate tracking the state of the theoretical machine to a very high degree of accuracy. This high level of accuracy enables tracking to within about one packet time.
While the apparatus and methods described by Parekh are notable advances to the art of network switching and routing, it is noted that his method requires a substantial number of arithmetical computations for efficient implementation in a high speed packet switch, using software or hardware techniques. Moreover, the PGPS technique of Parekh applies only to situations where packets are fully received before they can be forwarded. Unfortunately, the inability to forward packets before being fully received may render Parekh's method unsuitable for today's high-speed switches that necessarily require on-the-fly packet forwarding (also called cut-through forwarding).
In view of the foregoing, there is a need for fair queuing methods and apparatus that employ computationally efficient techniques to facilitate efficient hardware and software implementation.